package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/unique-paths/?envType=study-plan-v2&envId=top-100-liked
 * 组合数
 * 总共向下和向右的步数中选择向下或向右进行组合
 *
 * @author yulongtian
 * @create 2024-07-27 11:03
 */
public class Test90 {
    public static void main(String[] args) {

    }

    public int uniquePaths(int m, int n) {
        int len = m + n - 2;
        int high = Math.min(m - 1, n - 1);
        double fenmu = 1.0;
        double fenzi = 1.0;
        int temp_high = high;
        int temp_len = len;
        for (int i = 0; i < high; i++) {
            fenmu *= temp_high--;
            fenzi *= temp_len--;
        }

        return (int) (fenzi / fenmu);
    }

}
